Okay, also wo waren wir stehen geblieben? Es ging um die Implementierung des Simplex-Verfahren.

Also um die Frage, wie implementiere ich das Simplex-Verfahren eigentlich praktisch im Computer?

Worauf muss man achten? Was gibt es da für Kniffe, um ihn vielleicht noch ein bisschen

schneller zu machen? Und wir werden uns verschiedene Fragesteller angucken und

damit, wo wir gestern schon angefangen haben, war das Lösen von diesen linearen Gleichungssystemen.

Das ist euch ja in der Übung schon selber aufgefallen, dass man bei Simplex ziemlich

viele Gleichungssysteme lösen muss oder inverse Matrizen berechnen muss und dass das ziemlich

umständlich ist. Und auch wenn das ein Computer macht, ist das Problem immer noch, dass das

recht teuer ist, also dass das recht lange dauert. Also das Lösen von Gleichungssystemen

oder das Bilden einer inverse Matrix dauert sehr lange.

Also zum Beispiel so der bekannteste Algorithmus ist ja der Gauss-Algorithmus. Der hat eine

Laufzeit von O von N hoch 3, wobei, also wenn wir jetzt N Variablen haben oder das Beste,

was man momentan weiß, und wir fahren um eine inverse Matrix zu berechnen, ist O von

N Quadrat plus noch so ein bisschen. Und naja, wenn man sich das so anguckt, auf den ersten

Blick ist es natürlich polynomial in der Anzahl der Variablen, also N hoch 3 ist ja schon

ein Polynom, das ist ja okay, also theoretisch hat es eine polynomial Laufzeit, aber wenn

wir in jedem Schritt immer und immer wieder linearere Gleichungssysteme lösen, dann ist

halt N hoch 3 doch schon recht teuer. Also obwohl es polynomial ist, dauert es in der

Praxis schon recht lange, weil N hoch 3 ist jetzt nicht so das kleinste Polynom, was man

haben kann.

So, und wie gehen wir damit um? Also anstelle von Gauss machen wir ein bisschen was anderes,

wir machen nämlich eine LU-Faktorisierung. Das heißt, also wir wollen ja typischerweise

von unserer Basismatrix AB eine Inverse berechnen und bevor wir das machen, stellen wir erstmal

AB als L mal U da, wobei halt L eine untere Dreiecksmatrix ist und U eine obere Dreiecksmatrix.

So, und wenn wir jetzt das Gleichungssystem AB mal X gleich B lösen wollen, dann machen

wir das jetzt anders, also B ist AB mal X und A ist ja jetzt L mal U, dann nennen wir

dieses U mal X, nennen wir jetzt Y und dann lösen wir dieses Gleichungssystem in zwei

Schritten, nämlich als erstes lösen wir L mal Y gleich B und dann haben wir halt das

Y raus und dann müssen wir nur noch U mal X gleich Y berechnen.

Das heißt, wir haben jetzt unser ursprüngliches Gleichungssystem B gleich A mal X umgeschrieben

durch zwei Gleichungssysteme und das Gute daran ist, dass das L und das U ja jetzt Dreiecksgestalt

haben und dass man daher diese Gleichungssysteme schneller lösen kann als das ursprüngliche

Problem.

Es gibt bestimmte Pi-vot-Strategien, die stehen auch teilweise im Skript, mit denen man auch

noch erreichen kann, dass L und U ziemlich dünn besetzt sind, also dass da ziemlich viele

Nullen drin stehen und halt nur wenige Stellen, wo wirklich Einträge vorhanden sind.

Das Ganze kriegen wir jetzt dadurch schneller hin, nämlich nicht mehr in O von N hoch 3,

sondern in O von N², was wenigstens schon mal ein bisschen schneller ist als das, was wir vorher

hatten. Allerdings, O von N² ist jetzt immer noch nicht super, es ist ein bisschen besser als das,

was wir vorher hatten, allerdings immer noch nicht schnell genug.

Also wenn wir jetzt wirklich in jeder Iteration immer wieder mit einer L-U-Zerlegung unsere

Inverse bestimmen, ist das immer noch recht teuer und daher ist halt die Idee, nicht in jeder

Iteration eine Inverse zu bestimmen, sondern die Informationen, die wir durch vorherige Iterationen

haben, zu benutzen und sogenannte Update-Formeln zu entwickeln, die uns dann die neue Matrix quasi

ausrechnen, ohne sie explizit halt zu invertieren. So und da waren wir gestern stehengeblieben.

Nämlich wie sieht so eine Update-Formel aus. Also wenn wir uns jetzt mal zurück an den Simplex

erinnern und die Notation benutzen, da war ja J die eintretende Variable im Pricing und das Bi,

das war die verlassene Variable, die wir im Ratiotest bestimmt haben und dann gab es da

noch so ein Vektor W, das war der Vektor, den wir in F dran bestimmt haben und mit den drei

Sachen können wir jetzt eine Update-Formel herleiten und zwar sei so ein nk definieren wir uns, das ist